package com.jiang.专题.双指针.Q15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/20 14:07
 */
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // if (nums.length < 3)
        //     return new ArrayList<>();

        // Arrays.sort(nums);
        // HashMap<Integer, Integer> map = new HashMap<>();
        // List<List<Integer>> lists = new ArrayList<>();

        // for (int i = 0; i < nums.length; i++) {
        //     map.put(nums[i], i);
        // }

        // Integer k;
        // int target = 0;
        // for (int i = 0; i < nums.length; i++) {
        //     target = -nums[i];

        //     if (i > 0 && nums[i] == nums[i - 1]) {
        //         continue;
        //     }
        //     for (int j = i + 1; j < nums.length; j++) {
        //         if (j > i + 1 && nums[j] == nums[j - 1]) {
        //             continue;
        //         }

        //         /* map.get方法获取最后出现的值 */
        //         if ((k = map.get(target - nums[j])) != null) {
        //             if (k > j) {
        //                 lists.add(Arrays.asList(nums[i], nums[j], nums[k]));
        //             } else {
        //                 break;
        //             }
        //         }
        //     }
        // }
        // return lists;

        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();

        if (nums[0] > 0) {
            return lists;
        }

        for (int i = 0; i < nums.length - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int j = i + 1;
            int k = nums.length - 1;

            while (j < k) {
                int temp = nums[i] + nums[j] + nums[k];
                if (temp == 0) {
                    lists.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while (j < k && nums[j] == nums[j + 1])
                        j++;
                    while (j < k && nums[k] == nums[k - 1])
                        k--;
                    j++;
                    k--;
                } else if (temp > 0) {
                    k--;
                } else {
                    j++;
                }
            }
        }

        return lists;
    }
}
